# 剑指offer16.数值的整数次方
# 这样写会越界
class Solution(object):
    def myPow(self, x, n):
        result = float(1)
        if n == 0:
            return result
        elif n > 0:
            for i in range(1, n+1):
                result *= x
        else:
            for i in range(1, -n + 1):
                result *= x
            result = 1 / result
        return result


# 采用二分法
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0: return 0
        res = 1
        if n < 0: x, n = 1 / x, -n
        while n:
            # n & 1 ==> n % 2 == 1
            if n & 1: res *= x
            x *= x
            # n >>= 1 ==> n = n // 2
            n >>= 1
        return res

